/* 二分
* 
* 本题:
    下标映射原数组比较大小

*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5+10;

bool compare(int a, int b) {return a < b;} //传入数组下标，比较对应数组的元素大小

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1, 1); //哨兵
        for(int i = 2; i <= N; i++) //待插入元素下标
        {
            int l = 0, r = res.size() - 1;
            while(l <= r)
            {
                int mid = l + r >> 1;
                if(compare(res[mid],i)) l = mid + 1; //严格小于
                else r = mid - 1;
            }
            res.push_back(i);
            for(int j = res.size()-2; j > r; j--) swap(res[j], res[j+1]);//把i放到r上
            //if(compare(i, res[r])) swap(res[r], res[r+1]);
        }
        return res;
    }
};

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    
    return 0;
}